This protocol is a multicenter, randomized clinical study of the efficacy of four different regimens on the course of metastatic non-small-cell lung cancer (NSCLC). Metastatic NSCLC carries a very poor prognosis; current chemotherapy regimens prolong life in this setting by only six weeks. The overall survival of three experimental arms will be compared with the control arm (taxol plus cisplatin). A secondary goal is to estimate the response rate, time to progression, and toxicity of the various regimens. Patients will be randomly assigned to one of four drug regimens: A) taxol (135 mg/m2) plus cisplatin (75 mg/m2); B) gemcitabine (1000 mg/m2) plus cisplatin (100 mg/m2); C) taxotere (75 mg/m2) plus cisplatin (75 mg/m2); and D) carboplatin (AUC = 6.0) plus taxol (225 mg/m2). Gemcitabine and taxotere are analogs of currently available agents (ara-C and taxol).